package com.sheng.leetcode.year2022.month12.day10;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/12/10
 * <p>
 * 1691. 堆叠长方体的最大高度<p>
 * <p>
 * 给你 n 个长方体 cuboids ，<p>
 * 其中第 i 个长方体的长宽高表示为 cuboids[i] = [width i, length i, height i]（下标从 0 开始）。<p>
 * 请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。<p>
 * 如果 width i <= width j 且 length i <= length j 且 height i <= height j ，<p>
 * 你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。<p>
 * 返回 堆叠长方体 cuboids 可以得到的 最大高度 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]]<p>
 * 输出：190<p>
 * 解释：<p>
 * 第 1 个长方体放在底部，53 x 37 的一面朝下，高度为 95 。<p>
 * 第 0 个长方体放在中间，45 x 20 的一面朝下，高度为 50 。<p>
 * 第 2 个长方体放在上面，23 x 12 的一面朝下，高度为 45 。<p>
 * 总高度是 95 + 50 + 45 = 190 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：cuboids = [[38,25,45],[76,35,3]]<p>
 * 输出：76<p>
 * 解释：<p>
 * 无法将任何长方体放在另一个上面。<p>
 * 选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]<p>
 * 输出：102<p>
 * 解释：<p>
 * 重新排列长方体后，可以看到所有长方体的尺寸都相同。<p>
 * 你可以把 11x7 的一面朝下，这样它们的高度就是 17 。<p>
 * 堆叠长方体的最大高度为 6 * 17 = 102 。<p>
 * <p>
 * 提示：<p>
 * n == cuboids.length<p>
 * 1 <= n <= 100<p>
 * 1 <= widthi, lengthi, heighti <= 100<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-height-by-stacking-cuboids">1691. 堆叠长方体的最大高度</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1691 {

    @Test
    public void test01() {
        int[][] cuboids = {{50, 45, 20}, {95, 37, 53}, {45, 23, 12}};
//        int[][] cuboids = {{38,25,45},{76,35,3}};
//        int[][] cuboids = {{7,11,17},{7,17,11},{11,7,17},{11,17,7},{17,7,11},{17,11,7}};
        System.out.println(new Solution().maxHeight(cuboids));
    }
}

class Solution {
    public int maxHeight(int[][] cuboids) {
        int n = cuboids.length;
        // 针对每个长方体进行排序
        for (int[] cuboid : cuboids) {
            Arrays.sort(cuboid);
        }
        // 对长方体从小到大
        Arrays.sort(cuboids, (a, b) -> a[0] == b[0] ? (a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]) : a[0] - b[0]);
        // nums[i] 为以长方体 i 为底部时的最大高度
        int[] nums = new int[n];
        // 循环比较长方体
        for (int i = 0; i < n; ++i) {
            // 判断前一个长方体是否满足条件
            for (int j = 0; j < i; ++j) {
                if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
                    nums[i] = Math.max(nums[i], nums[j]);
                }
            }
            // 添加作为最底部的长方体的高度
            nums[i] += cuboids[i][2];
        }
        // 返回作为底部的长方体的最大高度
        return Arrays.stream(nums).max().getAsInt();
    }
}
